﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * 
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

     * */
    class Problem46 : IProblem
    {
        public string Calculate()
        {
            //taktika: krenut od početka, i sve primeove spremat u previousPrimes listu
            //za svaki broj koji nije prime, krenut od zadnjeg u listi, i oduzet od trenutnog broja
            //onda dok ne prekoracimo, pogledat jeli 2*n^2 za sve n-ove. Ako je jednak - slijedeći broj
            //ako je prekoraceno, idemo na niži prime i nastavljamo s istim n-om. Kad nema primeova i nije nađen - to je kraj

            List<int> previousPrimes = new List<int>() { 2 }; //2 cemo unaprijed dodat

            int x = 1;

            while (true)
            {
                x += 2; //samo neparne
                if (CommonFunctions.IsPrime(x))
                {
                    previousPrimes.Add(x);
                }
                else
                {
                    int n = 1;
                    bool found = false;
                    for (int i = previousPrimes.Count - 1; i >= 0; i--)
                    {
                        do
                        {
                            int difference = x - previousPrimes[i] - 2 * n * n;
                            if (difference == 0) //znači da je broj sastavljen od tih, pa izljećemo
                            {
                                found = true;
                                break;
                            }

                            if (difference < 0) //prekoračeno, idemo na slijedeći prime
                                break;

                            n++;

                        } while (true);

                        if (found)
                            break;
                    }

                    //ispalili smo sve primeove, ovo je rješenje ako nije pronadjen
                    if (!found)
                        break;
                }
            }


            return x.ToString();
        }
    }
}
